#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

class Solution1 {
public:
    const int mod = 1e9 + 7;

    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        int m = group.size();
        vector<vector<int>> dp(n + 1, vector<int>(minProfit + 1));
        for (int j = 0; j <= n; ++j) dp[j][0] = 1;
        for (int i = 0; i < m; ++i)
            for (int j = n; j >= group[i]; --j)
                for (int k = minProfit; k >= 0; --k)
                    dp[j][k] = (dp[j][k] + dp[j - group[i]][max(0, k - profit[i])]) % mod;

        return dp[n][minProfit];
    }
};

class Solution2 {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1);
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= n; ++i)
        {
            for (int j = 1; j <= i; ++j)
            {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
};

class Solution3
{
public:
    void solve()
    {
        int n;
        cin >> n;
        vector<vector<int>> v(3, vector<int>(n));
        for (int i = 0; i < 3; ++i)
            for (int j = 0; j < n; ++j)
            {
                cin >> v[i][j];
            }
        long long res = 0;
        for (int i = 0; i < 3; ++i) sort(v[i].begin(), v[i].end());
        for (int i = 0; i < n; ++i)
        {
            int left = 0; int right = n - 1;
            while (left < right)
            {
                int mid = left + (right - left + 1) / 2;
                if (v[0][mid] < v[1][i])
                    left = mid;
                else
                    right = mid - 1;
            }
            int one = left;
            if (v[0][left] >= v[1][i]) one = -1;
            left = 0; right = n - 1;
            while (left < right)
            {
                int mid = left + (right - left) / 2;
                if (v[2][mid] > v[1][i])
                    right = mid;
                else
                    left = mid + 1;
            }
            int three = right;
            if (v[2][right] <= v[1][i]) three = n;
            res += 1LL * (one + 1) * (n - three);
        }

        cout << res;
    }
};

class ThroneInheritance {
public:
    unordered_map<string, vector<string>> t;
    unordered_set<string> dead;
    vector<string> res;

    ThroneInheritance(string kingName) {
        t["kingname"].push_back(kingName);
    }

    void birth(string parentName, string childName) {
        t[parentName].push_back(childName);
    }

    void death(string name) {
        dead.insert(name);
    }

    void dfs(const string& cur)
    {
        for (auto& c : t[cur])
        {
            if (dead.find(c) == dead.end())
                res.push_back(c);
            dfs(c);
        }
    }

    vector<string> getInheritanceOrder() {
        res.resize(0);
        dfs("kingname");
        return res;
    }
};


int main()
{

    return 0;
}